/*
 * kdtree.h
 *
 *  Created on: Mar 3, 2011
 *      Author: tqlong
 */

#ifndef KDTREE_H_
#define KDTREE_H_

#include "tree.h"
#include <limits>

/** Node statistics need to implement
 *    combine()       to combine children statistics
 *    accumulate()    to compute statistics at leaf nodes
 *    lowerBound()    to compute lower bound of a point
 */
template<typename T>
class BoundingBox
{
public:
  typedef T                              vec_type;
  vec_type minBox_, maxBox_;
  int n_;

  BoundingBox() : n_(0) {}

  void combine(const std::vector<BoundingBox*> &child_boxes);
  void accumulate(const vec_type &p);
  double lowerBound(const vec_type &p);
  double boxLowerBound(const BoundingBox &b);
  void print();
};

template<typename T, typename NS>
class KDTreeNode : public TreeNode<T>
{
public:
  typedef TreeNode<T>                    __Base;
  typedef NS                             nodestats_type;
  typedef typename __Base::iset_type     iset_type;
  typedef typename __Base::pset_type     pset_type;
  typedef typename __Base::vec_type      vec_type;
  typedef typename __Base::nodelist_type nodelist_type;
protected:
  nodestats_type nstats_;
  double upper_bound_;
public:
  /** Root constructor */
  KDTreeNode(pset_type& p, iset_type& idx)
    : __Base(p, idx) {}
  /** Child constructor */
  KDTreeNode(KDTreeNode& parent, int lo, int hi_ex)
    : __Base(parent, lo, hi_ex) {}
  KDTreeNode* child(unsigned int i) const { return static_cast<KDTreeNode*>(__Base::child(i)); }

  /** Tree build functions */
  void prepareRoot() {};
  void split();
  void splitRecursive();
protected:
  bool split(int d);
  void combineStatistics();
  void setUpperBound(double u);
  static double median5(std::vector<double>& x, int i, int n);
  static double median(std::vector<double>& x, int n);
public:
  static void nearest(const vec_type& p, KDTreeNode& Q, double &bound, int& minIdx);
  static int nearest(const vec_type& p, KDTreeNode& root);
  static void allNearest(KDTreeNode& P, KDTreeNode& Q, std::vector<int>& minIdx, std::vector<double>& minDist);
  static void allNearest(KDTreeNode& P, KDTreeNode& Q, std::vector<int>& minIdx);
  void print();
};

#include "kdtree_impl.h"
#endif /* KDTREE_H_ */
